package _11_整理题目._4_动态规划._买卖股票;


import org.junit.Test;

/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/
 *
 * 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
 * 在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。
 * 你也可以先购买，然后在 同一天 出售。
 * 返回 你能获得的 最大 利润。
 *
 * 1、动态规划，自底向上
 *
 *
 * 2、动态规划，滚动数组
 *
 */
public class _03_买卖股票的最好时机_2 {

    public int maxProfit1(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        for(int i=1; i<n; i++) {
            dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]+prices[i]);
            dp[i][1] = Math.max(dp[i-1][0]-prices[i], dp[i-1][1]);
        }
        return dp[n-1][0];
    }

    public int maxProfit2(int[] prices) {
        int n = prices.length;
        int[] a = new int[2];
        a[0] = 0;
        a[1] = -prices[0];
        for(int i=1; i<n; i++) {
            int[] b = new int[2];
            b[0] = Math.max(a[0], a[1]+prices[i]);
            b[1] = Math.max(a[0]-prices[i], a[1]);
            a = b;
        }
        return a[0];
    }

    @Test
    public void main() {
        int[] prices = {7,1,5,3,6,4};
        System.out.println(maxProfit1(prices));
        System.out.println(maxProfit2(prices));
    }
}
